﻿#pragma once
#include "Index.h"

class ICutRope
{
public:
	/**
	 * 剪绳子(进阶版).
	 * https://www.nowcoder.com/practice/106f666170554379ab1974e5a601e741?tpId=265&tqId=39276&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D2%26tpId%3D13%26type%3D265%3Ftag%3D1292&difficulty=undefined&judgeStatus=undefined&tags=&title=
	 *
	 * 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），
	 * 每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？
	 *
	 * 例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。
	 *
	 * 由于答案过大，请对 998244353 取模。
	 * 数据范围：2≤n≤10^14
	 * 进阶：空间复杂度O(1) ， 时间复杂度O(logn)
	 */
	virtual long long CutRope(long long number) = 0;
};

class CutRope
{
public:
	class DP:public ICutRope
	{
	public:
		//动态规划解法 时间:O(n^2) 空间:O(n)
		long long CutRope(long long number) override
		{
			if (number <= 0)
				return 0;
			switch (number)
			{
			case 1: return 1;
			case 2: return 1;
			case 3: return 2;
			case 4: return 4;
			case 5: return 6;
			}
			//dp[i]表示将长度为i的绳子切成若干份后可以获得的最大乘积
			//dp[i]=max{dp[k][i-k],k∈[1,i/2]}
			std::vector<long long> dp(number + 1, 1);
			dp[1] = 1;
			dp[2] = 2;
			dp[3] = 3;
			dp[4] = 4;
			dp[5] = 6;
			for (int i = 6; i <= number; ++i)
			{
				for (int j = 1; j <= (i >> 1); ++j)
				{
					dp[i] = std::max<long long>(dp[j] * dp[i - j], dp[i]);
				}
				dp[i] %= 998244353;
			}

			return dp[number];
		}
	};
	class Greedy:public ICutRope
	{
	public:
		//贪心、快速幂解法 时间:O(logn) 空间:O(1)
		long long CutRope(long long number) override
		{
			if (number <= 0)
				return 0;
			switch (number)
			{
			case 1: return 1;
			case 2: return 1;
			case 3: return 2;
			case 4: return 4;
			case 5: return 6;
			}
			const long long modNum = 998244353;
			const long long timeOfThree = number / 3;
			long long result = 0;
			switch (number % 3)
			{
			case 0:
				result = PowWithMod<long long>(3, timeOfThree, modNum);
				break;
			case 1:
				result = PowWithMod<long long>(3, timeOfThree - 1, modNum) * 4;
				break;
			case 2:
				result = PowWithMod<long long>(3, timeOfThree, modNum) * 2;
				break;
			}
			return result % modNum;
		}
	private:
		/// <summary>
		/// 带取模的快速幂
		/// </summary>
		template<typename T>
		static T PowWithMod(T base, size_t exponent, T mod)
		{
			if (base == 0)
				return 0;
			if (exponent == 0)
				return 1;
			else if (exponent == 1)
				return base % mod;

			T result = PowWithMod(base, exponent >> 1, mod);
			if ((exponent & 0x1) == 0)
				result = (result * result) % mod;
			else
				result = (result * result * base) % mod;

			return result;
		}
	};

	class Review:public ICutRope
	{
	public:
		//如果绳子的长度大于4,尽量分解出长度为3的绳子出来
		//57=> 1162261467
		long long CutRope(long long number) override
		{
			if (number <= 0)
				return 0;
			long long ans = 1;
			while(number>4)
			{
				ans *= 3;
				ans %= INT_MAX;
				number -= 3;
			}
			switch (number)
			{
			case 2: ans *= 2; break;
			case 3: ans *= 3; break;
			case 4: ans *= 4; break;
			}
			ans %= INT_MAX;
			return ans;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class CutRopeTest:public SolutionTestor<ICutRope>
{
protected:
	void LoadSolutions(::std::vector<::ICutRope*>& solutions) override
	{
		solutions = {
			new CutRope::DP,
			new CutRope::Greedy,
		};
	}
};

TEST_F(CutRopeTest, CutRope)
{
	CutRope::DP expectSolution;
	TestForSolutions([&expectSolution](ICutRope* solution)
	{
		for (int roleLength = 1; roleLength <= 100; ++roleLength)
		{
			const auto expectResult = expectSolution.CutRope(roleLength);
			const auto result = solution->CutRope(roleLength);
			EXPECT_EQ(result, expectResult) << "roleLength:" << roleLength;
		}
	});
}
#endif
